package leetcode.doublepointer;

//82. 删除排序链表中的重复元素 II
public class DeleteDuplicates {

    //「相同节点一个不保留」
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        ListNode temp = head;
        while (temp != null) {
            // 进入循环时，确保了 head 不会与上一节点相同
            if (temp.next == null || temp.val != temp.next.val) {
                tail.next = temp;
                tail = tail.next;
            }
            // 如果 head 与下一节点相同，跳过相同节点
            while (temp.next != null && temp.next.val == temp.val) {
                temp = temp.next;
            }
            temp = temp.next;
        }
        tail.next = null;
        return dummy.next;
    }

    //「相同节点保留一个」
    public ListNode deleteDuplicates2(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        ListNode temp = head;
        while (temp != null) {
            while (temp.next != null && temp.val == temp.next.val) {
                temp = temp.next;
            }
            tail.next = temp;
            tail = tail.next;
            temp = temp.next;
        }
        tail.next = null;
        return dummy.next;
    }

    public ListNode deleteDuplicates22(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode dummy = new ListNode(-109);
        ListNode tail = dummy;
        ListNode temp = head;
        while (temp != null) {
            // 值不相等才追加，确保了相同的节点只有第一个会被添加到答案
            if (tail.val != temp.val) {
                tail.next = temp;
                tail = tail.next;
            }
            temp = temp.next;
        }
        tail.next = null;
        return dummy.next;
    }

    //二战、相同结点一个不留
    public ListNode deleteDuplicatesP(ListNode head) {
        //自定义一个头结点
        ListNode my = new ListNode(0);
        ListNode tail = my;
        ListNode temp = head;
        //开始移动
        while (temp != null) {
            //不相等的，直接连上
            if (temp.next == null || temp.val != temp.next.val) {
                tail.next = temp;
                tail = tail.next;
            }
            //由于是升序，而且可能不止一个重复数据，所以使用while循环控制移动
            while (temp.next != null && temp.val == temp.next.val) {
                temp = temp.next;
            }
            temp = temp.next;
        }
        tail.next = null;

        return my.next;
    }
}

